/*
 * @lc app=leetcode.cn id=208 lang=golang
 *
 * [208] 实现 Trie (前缀树)
 */

// @lc code=start

type Trie struct {
	Val  rune
	Data bool // 表示是否为单词
	Next []*Trie
}

/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{0, false, make([]*Trie, 0)}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
	curTrie := this
	visit := this.Next
	wordR := []rune(word)
	n := len(wordR)
	cur := 0
	// var curTrie *Trie
	for len(visit) != 0 {
		isFind := false
		for _, v := range visit {
			if cur == n {
				curTrie.Data = true
				return
			}
			if v.Val == wordR[cur] {
				cur++
				visit = v.Next
				curTrie = v
				isFind = true
				break
			}
		}
		if !isFind {
			break
		}
	}

	wordR = wordR[cur:]
	root := &Trie{}
	head := root
	isLast := false
	for i, v := range wordR {
		if i == len(wordR)-1 {
			isLast = true
		}

		tmp := make([]*Trie, 1)
		tmp[0] = &Trie{Val: v, Data: isLast}
		head.Next = append(head.Next, tmp...)
		head = tmp[0]
		// fmt.Println(string(v), string(head.Val), head.Data)
	}
	// head.Data = true
	curTrie.Next = append(curTrie.Next, root.Next...)
	return

}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
	curTrie := this
	visit := this.Next
	wordR := []rune(word)
	n := len(wordR)
	cur := 0
	// var curTrie *Trie
	for len(visit) != 0 {
		isFind := false
		for _, v := range visit {
			// fmt.Println(v.Data, string(v.Val), curTrie.Data, string(curTrie.Val))
			if cur == n {
				return curTrie.Data
			}
			if v.Val == wordR[cur] {
				cur++
				visit = v.Next
				curTrie = v
				isFind = true
				break
			}
		}
		if !isFind {
			break
		}
	}
	// fmt.Println(cur, n, string(curTrie.Val))
	if cur == n && curTrie.Val == wordR[cur-1] {
		return curTrie.Data
	}
	return false
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
	curTrie := this
	visit := this.Next
	wordR := []rune(prefix)
	n := len(wordR)
	cur := 0
	// var curTrie *Trie
	for len(visit) != 0 {
		isFind := false
		for _, v := range visit {
			if cur == n {
				return true
			}
			if v.Val == wordR[cur] {
				cur++
				visit = v.Next
				curTrie = v
				isFind = true
				break
			}
		}
		if !isFind {
			break
		}
	}
	if cur == n && curTrie.Val == wordR[cur-1] {
		return true
	}
	return false
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */
// @lc code=end
